package org.regotto.basics.bfs;

import org.regotto.common.Utils;

import java.util.Scanner;

/**
 * 图层次遍历 bfs
 * 拉链存储图数据
 */
public class GraphLevelTraversal {

    static final int N = 100;
    static int[] h = new int[N], ne = new int[N], e = new int[N], d = new int[N], q = new int[N];
    static int idx, n, m, hh, tt;

    static void add(int a, int b) {
        e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
    }

    static int bfs() {
        q[0] = 1;
        Utils.full(d, -1);
        d[1] = 0;
        while (hh <= tt) {
            int t = q[hh++];
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                if (d[j] == -1) {
                    d[j] = d[t] + 1;
                    q[++tt] = j;
                }
            }
        }
        return d[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //m个点 n条边
        n = sc.nextInt();
        m = sc.nextInt();
        Utils.full(h, -1);
        for (int i = 0; i < m; i++) {
            add(sc.nextInt(), sc.nextInt());
        }
        System.out.println(bfs());
    }

}
